package Leetcode.排序;

import java.util.Arrays;

public class CountingSort {

    // 计数排序函数
    public static void countingSort(int[] array) {
        // 找出数组中的最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }

        // 创建计数数组，其长度是最大值加1
        int[] countArray = new int[max + 1];
        
        // 计算每个元素出现的次数
        for (int j : array) {
            countArray[j]++;
        }

        // 修改countArray，每个位置存储小于等于该值元素的个数
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }

        // 创建输出数组，长度与原始数组相同
        int[] outputArray = new int[array.length];

        // 将每个元素放置到其正确的位置
        for (int i = array.length - 1; i >= 0; i--) {
            outputArray[countArray[array[i]] - 1] = array[i];
            countArray[array[i]]--;
        }

        // 将排序好的数组复制回原数组
        System.arraycopy(outputArray, 0, array, 0, array.length);
    }

    // 主函数，用于测试计数排序
    public static void main(String[] args) {
        int[] array = {4, 2, 2, 8, 3, 3, 1};
        countingSort(array);
        System.out.println(Arrays.toString(array));

    }
}
